package homework;

import java.util.*;

class TreeNode {
    public int val;
    public TreeNode left;//左孩子的引用
    public TreeNode right;//右孩子的引用

    public TreeNode(int val) {
        this.val = val;
    }
}
public class HomeWork32 {
    //前序遍历
    static void pre_print(TreeNode root){
        if(root==null){
            System.out.println("节点为空");
            return ;
        }
        Queue<TreeNode> stack=new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node=stack.poll();
            System.out.print(node.val+" ");
            if(node.left!=null) stack.add(node.left);
            if(node.right!=null) stack.add(node.right);
        }
    }
    //中序遍历
    static void mid_print(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        while (!stack.empty()||root!=null){
            if(root!=null){
                stack.add(root);
                root= root.left;
            }else {
                root=stack.pop();
                System.out.print(root.val+" ");
                root=root.right;
            }
        }
    }
    //后序遍历
    static void last_print(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> s=new Stack<>();
        TreeNode last=null;
        while (!s.isEmpty()||root!=null){
            while (root!=null){
                s.push(root);
                root=root.left;
            }
            if(!s.isEmpty()){
                TreeNode t=s.pop();
                if(t.right==null||last==t.right){
                    System.out.print(t.val+" ");
                    last=t;
                }else{
                    s.push(t);
                    root=t.right;
                }
            }
        }
    }
    //求树的最大高度
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 1;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    //二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode>stack=new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()){
            int k=stack.size();
            List<Integer> list1=new ArrayList<>();
            for (int i = 0; i <k ; i++) {
                TreeNode tmp=stack.poll();
                if(tmp.left!=null) stack.add(tmp.left);
                if(tmp.right!=null) stack.add(tmp.right);
                list1.add(tmp.val);
            }
            list.add(list1);
        }
        return list;
    }
    //合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null){
            return root2;
        }
        if(root2==null){
            return root1;
        }
        TreeNode merge=new TreeNode(root1.val+root2.val);
        merge.left=mergeTrees(root1.left,root2.left);
        merge.right=mergeTrees(root1.right,root2.right);
        return merge;
    }
    //求二叉树的最大宽度
    public int widthOfBinaryTree(TreeNode root) {
        if(root!=null){
            return 0;
        }
        int max=0;
        Queue<TreeNode>stack=new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()){
            int k=stack.size();
            max=Math.max(k,max);
            List<Integer> list1=new ArrayList<>();
            for (int i = 0; i <k ; i++) {
                TreeNode tmp=stack.poll();
                if(tmp.left!=null) stack.add(tmp.left);
                if(tmp.right!=null) stack.add(tmp.right);
                list1.add(tmp.val);
            }
        }
        return max;
    }
    public static void main(String[] args) {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');

        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        E.right = H;
        last_print(A);
    }
//    先序遍历
//
//            中序遍历
//
//    后序遍历
//
//            求节点个数
//
//    求叶子节点的个数
//
//            求第k层节点的个数
//
//    查找节点
}
